package leetcode.templates.kmp;

import leetcode.helper.H;

public class FunctionZ {
	public void z0(String s) {
		int len = s.length();
		int[] z = new int[len];
		int L = 0, R = 0, r = 0;
		z[0] = len;
		for (int i = 1; i < len; i++) {
			z[i] = i > R ? 0 : Math.min(z[i - L], R - i + 1);
			while ((r = i + z[i]) < len && s.charAt(z[i]) == s.charAt(r)) {
				L = i;
				R = r;
				z[i]++;
			}
		}
		H.print(z);
	}

	public void z1(String s) {
		s = "#" + s;
		int len = s.length();
		int[] z = new int[len];
		int L = 1, R = 0, r = 0;
		z[1] = len - 1;
		for (int i = 2; i < len; i++) {
			z[i] = i > R ? 0 : Math.min(z[i - L + 1], R - i + 1);
			while ((r = i + z[i]) < len && s.charAt(z[i] + 1) == s.charAt(r))
				z[i]++;
			if (r - 1 > R) {
				L = i;
				R = r - 1;
			}
		}
		H.print(z);
	}

	public static void main(String[] args) {
		FunctionZ z = new FunctionZ();
		z.z0("abcabcaa");
		z.z1("abcabcaa");
		z.z0("aaaa");
		z.z1("aaaa");
		z.z0("azbazbzaz");
		z.z1("azbazbzaz");
		z.z0("babab");
		z.z1("babab");
	}
}
